/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/generalized-abbreviation
   @Language: C++
   @Datetime: 19-04-24 11:20
   */

// Method 1
class Solution {
	vector<int> getone(int num, int len){
		vector<int> v;
		int count=0;
		for(int i=len; i--; num>>=1){
			if(num&1) ++count;
			else {
				v.push_back(count);
				if(count) v.push_back(0);
				count=0;
			}
		}
		if(count) v.push_back(count);
		reverse(v.begin(),v.end());
		return v;
	}
public:
	/**
	 * @param word: the given word
	 * @return: the generalized abbreviations of a word
	 */
	vector<string> generateAbbreviations(string &word) {
		// Write your code here
		vector<string> vs;
		char str[32];
		for(int i=0; i<(1<<word.length()); ++i){
			vector<int> v=getone(i,word.length());
			string abbr;
			for(int pos=0, j=0; j<v.size(); ++j){
				if(v[j]==0) abbr.push_back(word[pos++]);
				else {
					sprintf(str,"%d",v[j]);
					abbr.append(str);
					pos+=v[j];
				}
			}
			vs.push_back(abbr);
		}
		return vs;
	}
};


// Method 2
class Solution {
public:
	/**
	 * @param word: the given word
	 * @return: the generalized abbreviations of a word
	 */
	vector<string> generateAbbreviations(string &word) {
		// Write your code here
		vector<string> vs;
		for(int i=0; i<(1<<word.length()); ++i){
			string abbr;
			int count=0;
			for(int j=0; j<word.length(); ++j){
				if((i>>j)&1) ++count;
				else{
					if(count) abbr.append(to_string(count));
					count=0;
					abbr.push_back(word[j]);
				}
			}
			if(count) abbr.append(to_string(count));
			vs.push_back(abbr);
		}
		return vs;
	}
};
